One of known encoding methods used for movie compression recording is H.264/MPEG-4 AVC (hereinafter, “H.264”) (ITU-T H.264 (03/2010) Advanced video coding for generic audio visual services). According to H.264, each picture can be divided into a plurality of slices and image data can be encoded on a slice-by-slice basis. The slices have little dependence on one another. Accordingly, the slices can be subjected to encoding or decoding in parallel. One of significant benefits of the division into slices is that the execution of parallel processing by, for example, a multicore CPU enables reduction of processing time.
Furthermore, each slice is encoded by a related-art binary arithmetic encoding scheme used in H.264. Specifically, each syntax element is binarized, thus generating a binary signal. Each syntax element is assigned the probability of occurrence as a table (hereinafter, “probability table”) in advance. The binary signal is subjected to arithmetic encoding based on the probability table. The probability table is used as decoding information for decoding subsequent symbols during decoding and is used as encoding information for encoding subsequent symbols during encoding. Each time encoding is performed, the probability table is updated based on statistical information indicating whether the encoded binary signal is a symbol assigned higher probability or not.
Recently, activities for international standardization of higher-efficiency encoding as a successor to H.264 have been started and Joint Collaborative Team on Video Coding (JCT-VC) has been established by ISO/IEC and ITU-T. According to JCT-VC, the standardization of High Efficiency Video Coding (HEVC) is in progress.
For the standardization of HEVC, various encoding tools have been broadly examined from viewpoints of not only improvement of encoding efficiency but also ease of implementation and reduction of processing time. For reduction of processing time, schemes for enhancing parallelism have been examined. One of them is a scheme, called Wavefront, for parallel entropy encoding/decoding (JCT-VC document JCTVC-I1003.doc, the Internet <http://phenix.int-evey.fr/jct/doc). Since a target binary signal to be encoded has to be encoded using the probability table updated constantly, parallel processing cannot be performed if statistical information is not reset. If the statistical information is reset, the encoding efficiency is unfortunately reduced. On the other hand, according to Wavefront, the probability table upon encoding of a plurality of blocks at predetermined positions is used for the left block in the next line, thus achieving parallel encoding of blocks on a line-by-line basis while preventing a reduction in encoding efficiency. Although Wavefront has been mainly described with respect to encoding, the same applies to decoding.
According to HEVC, the schemes for enhancing the parallelism include tiling. According to this technique, tiles allow a picture to be divided into rectangular regions that can independently be processed. Thus, high throughput can be achieved by parallel encoding/decoding and the capacity of a memory included in each of an encoding apparatus and a decoding apparatus can be reduced.
According to HEVC, processing, such as tiling or Wavefront, has been exclusively performed using a symbol tiles_or_entropy_coding_sync_idc. If the symbol has a value of 0, this means that a picture is composed of a single tile and Wavefront parallel processing is not performed. If the symbol has a value of 1, this means that the picture is composed of a plurality of tiles but Wavefront parallel processing is not performed. If the symbol has a value of 2, this means that the picture is composed of a single tile and parallel processing, such as Wavefront, is performed. If the symbol has a value of 3, this means that the picture is composed of a single tile, Wavefront parallel processing is not performed, and entropy slices which can independently be decoded are used. Other values cannot be used. The reason is as follows. If a plurality of processes are performed in parallel on a sufficiently low definition image, controlling such parallel processing would be complicated. Because the degree of complexity would be too high for the picture size, exclusive processing is performed. In particular, real-time decoding of a very large image, such as an 8 k or 4 k image, requires high parallelism. The parallelism can be enhanced by dividing the image into very small tiles, but the encoding efficiency is reduced because information available for prediction is limited at the boundary between tiles. Wavefront parallel processing performed on such a very large image divided into block lines requires a large-capacity line buffer and, unfortunately, does not enable the parallelism to be enhanced more than that using tiles, because the block lines have a dependence on each other, the dependence including the probability table. As regards such a large image, it is necessary to divide the image into segments having a certain size, allocate the segments to computer nodes, and operate a plurality of processors for each node. For example, in the case where tiles are allocated to nodes and processing is performed on a node-by-node basis, unfortunately, parallel processing, such as Wavefront, cannot be performed in the tiles.
The present invention provides an encoding format that enables multi-stage parallel processing to enhance parallelism of processes and achieve high-speed encoding and decoding.